package com.example.hot100;

import java.util.*;

/**
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 *  异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 *
 *  示例 1:
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 *
 *  示例 2:
 * 输入: s = "abab", p = "ab"
 * 输出: [0,1,2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 */
public class Leetcode438_FindAnagrams {
    public static void main(String[] args) {
        String s;
        String p;
        s = "cbaebabacd";
        p = "abc";

//        s = "abab";
//        p = "ab";
        System.out.println(new Solution().findAnagrams(s, p));
    }

    static class Solution {
        /**
         * 使用双指针标识窗口的左右边界
         * @param s
         * @param p
         * @return
         */
        private List<Integer> findAnagrams3(String s, String p) {
            List<Integer> res = new ArrayList<>();
            char[] sChars = s.toCharArray();
            char[] pChars = p.toCharArray();
            int[] sCounts = new int[26];
            int[] pCounts = new int[26];
            int pLen = pChars.length;
            if (pLen > sChars.length) return res;

            for (int i = 0; i < pLen; i++) { // 统计p字符串中各个字符的个数
                pCounts[(pChars[i] - 'a')]++;
            }

            int left = 0, right = 0;
            while (right < sChars.length) {
                int curRightIndex = sChars[right] - 'a';
                sCounts[curRightIndex]++;
                // right当前遍历到的字符加入sCounts后不满足p的字符数量要求
                System.out.println("right: " + right);
                while (sCounts[curRightIndex] > pCounts[curRightIndex]) {
                    int curLeftIndex = sChars[left] - 'a';
                    sCounts[curLeftIndex]--;
                    System.out.println("left : " + left);
                    left++;
                }
                System.out.println("================");

                if (right - left + 1 == pLen) res.add(left);

                right++;
            }
            return res;
        }

        /**
         * 滑动窗口 + 数组
         * 字符串中的字符全是小写字母，可以用长度为26的数组记录字母出现的次数
         * 窗口向前滑动一次，窗口中的元素减一加一 窗口最前面的元素移除;窗口最后面的元素加入
         * @param s
         * @param p
         * @return
         */
        private List<Integer> findAnagrams2(String s, String p) {
            List<Integer> res = new ArrayList<>();
            char[] sChars = s.toCharArray();
            char[] pChars = p.toCharArray();
            int[] sCounts = new int[26];
            int[] pCounts = new int[26];
            int pLen = pChars.length;
            if (pLen > sChars.length) return res;
            for (int i = 0; i < pLen; i++) { // 初始化窗口sCounts代表窗口
                sCounts[(sChars[i] - 'a')]++;
                pCounts[(pChars[i] - 'a')]++;
            }
            if (Arrays.equals(pCounts, sCounts)) res.add(0);
            for (int i = pLen; i < sChars.length; i++) { // 窗口向前移动一位，窗口中的元素减一加一
                sCounts[sChars[i - pLen] - 'a']--; // 窗口最前面的元素移除
                sCounts[sChars[i] - 'a']++; // 窗口最后面的元素加入
                if (Arrays.equals(sCounts, pCounts)) res.add(i - pLen + 1);
            }

            return res;
        }

        /**
         * 解法一：滑动窗口 + hashmap
         * @param s
         * @param p
         * @return
         */
        private List<Integer> findAnagrams1(String s, String p) {
            List<Integer> res = new ArrayList<>();
            char[] pChars = p.toCharArray();
            Map<Character, Integer> pMap = new HashMap<>();
            for (int i = 0; i < pChars.length; i++) {
                pMap.put(pChars[i], pMap.getOrDefault(pChars[i], 0) + 1);
            }
            char[] sChars = s.toCharArray();
            for (int i = 0; i <= sChars.length - pChars.length; i++) {
                Map<Character, Integer> window = getWindowMap(sChars, i, pChars.length);
                if (isSameMaps(window, pMap)) res.add(i);
            }
            return res;
        }

        private boolean isSameMaps(Map<Character, Integer> map1, Map<Character, Integer> map2) {
            Set<Map.Entry<Character, Integer>> entries = map2.entrySet();
            for (Map.Entry<Character, Integer> entry : entries) {
                char key = entry.getKey();
                int value = entry.getValue();
                if (!map1.containsKey(key) || !(map1.get(key) == value)) return false;
            }
            return true;
        }

        private Map<Character, Integer> getWindowMap(char[] chars, int start, int len) {
            Map<Character, Integer> window = new HashMap<>();
            for (int i = start; i < start + len; i++) {
                window.put(chars[i], window.getOrDefault(chars[i], 0) + 1);
            }
            return window;
        }

        public List<Integer> findAnagrams(String s, String p) {
            return findAnagrams3(s, p);
        }
    }
}
